1. Field of Invention
This invention relates to systems and methods for processing images using filters. More specifically, this invention relates to systems and methods for designing image processing filters using templates with optimality criterion based on aspects of human visual perception.
2. Description of Related Art
A wide variety of digital document processing tasks are performed using template-based filters. Illustratively, digital document processing tasks include resolution conversion, enhancement, restoration, appearance tuning and de-screening of images. These tasks are commonly performed on monochrome and color images, as well as binary and continuous tone images. A continuous tone image may also be referred to as a grayscale image.
In conventional systems and methods, a typical filter includes template operators to perform filtering of the images. That is, a filter may be characterized as an operator or device that transforms one image into another image. The filter is formed of a number of imaging template operators or templates. These templates may be, for example, stored in a look-up table. The number of templates in a filter may vary between a small number of templates to thousands of templates. Accordingly, a look-up table is typically used to implement a filter.
A raster is a one-dimensional array of image data, reflecting a single line of data across a single dimension, i.e., the length or the width, of the image. Further, each location in an image may be called a pixel. In an array defining an image in which each item of data provides a value, each value indicating the properties of a location may be called a pixel value. Each pixel value is a bit in a binary form of an image, a grayscale value in a grayscale form of an image, or a set of color spaced coordinates in a color coordinate form of an image. The binary form, grayscale form, and color coordinate form are each arranged in a two-dimensional array, which defines an image.
The filter, using the templates, transforms certain observed pixel patterns in a binary image, for example, into a corresponding enhanced binary pixel pattern, for example. Specifically, the filter observes an arrangement of pixels using a suitable window or mask. A window is an imaging component that observes a plurality of pixels at the same time and inputs properties of the observed pixels. After observing the arrangement of pixels, the filter then attempts to match the observed pixel pattern with one of the templates in the look-up table. If the look-up table contains a match to the observed pixel pattern, the look-up table generates an appropriate output. The output may be an enhanced pixel pattern that corresponds to the observed pixel pattern.
A wide variety of types and sizes of observation windows or masks are known. The particular window used in a particular application depends on the image to be analyzed and the particular process to be performed on the image. Illustratively, a 3xc3x973 window may be used to process an image. The 3xc3x973 window, at various locations in the image, observes a 3xc3x973 block, i.e., a 9-pixel block, of binary-valued pixels, for example. One pixel in the window is the target pixel, which is typically the center pixel, while the other pixels in the window are the neighboring pixels. The target pixel and the neighboring pixels result in a neighborhood. The window is typically scanned across an image advancing from target pixel to target pixel.
After the neighborhood is observed in the window, the neighborhood is then processed in some manner. For example, the observed neighborhood may be transformed into a vector. The vector is expressed in the form of (A1, A2 . . . An) and is used to represent the properties of the target pixel, including the neighborhood of the target pixel. Each element of the vector represents one of the pixels observed in the window. The vector is then used in the look-up table to generate a desired output, for example.
A look-up table may be created in a wide variety of ways. Typically, an input value is input into the look-up table and, in response, the look-up table outputs an output value. Further, the look-up table is typically created using a training image or a set of training images. Restoration and Enhancement of Digital Documents, by R. Loce and E. Dougherty, teaches a variety of methods for designing templates based on sets of training images. The training image will occur in pairs, where one member is the xe2x80x9ctypically input image,xe2x80x9d or the xe2x80x9ctypically observed image,xe2x80x9d i.e., the xe2x80x9cobserved image,xe2x80x9d and the other image is the xe2x80x9cideal desired processed version of the image,xe2x80x9d i.e., the xe2x80x9cideal image.xe2x80x9d The training image pairs may be input into a computer program that acquires and analyzes pattern statistics between the two images, i.e., using computer-aided filter design techniques.
Conventional computer-aided filter design may be accomplished through using training-sets of document bitmaps, for example. A bitmap is a binary digital image whose pixels possess values of 0 or 1. Alternatively, conventional computer-aided filter design may be accomplished through the use of training-sets of a binary half-toned image and a grayscale image. Specifically, one member of a set of training images is a binary half-toned image, and the other member is the original grayscale, i.e., the original image used to generate the binary halftoned image. In this case, the xe2x80x9ctypically observed imagexe2x80x9d is the halftone image, and the ideal output of a de-screening filter would be the original gray-scale image.
Illustratively, for a given pattern that occurs in the binary image about a target pixel, a training analysis systelm examines a target pixel at that corresponding location in the gray-scale image. The center of the window may be placed at the target pixel, for example. Based on the set of grayscale pixels associated with corresponding target pixel in the grayscale image, a xe2x80x9cbest grayscale pixel valuexe2x80x9d is determined for the target pixel. In other words, a template is created for the target pixel in the binary image. This analysis is performed for all binary patterns that are significant.
In this process of template selection, significance may be due to either the pixel pattern""s frequency of occurrence, the pattern""s effect on the generated image, or both. Accordingly, if a template, i.e., a pattern of pixels in the binary image, is observed and considered significant, the observed target pixel value will be assigned or associated with a certain value, i.e., a corresponding grayscale value. Both the observed value and the corresponding grayscale value are stored in the look-up table. Accordingly, the look-up table accepts an input value and outputs a desired corresponding output value, i.e., maps an input value to a desired corresponding output value.
However, it should be apparent that this input/output process may be performed in various other ways without using a look-up table. One alternative approach that is equivalent to using a look-up table representation is a Boolean logic representation. In the Boolean logic representation, pixel values are used as variables in the logic architecture, such as a logical sum of products. The goal of template filter design using Boolean logic representation is to derive statistically-optimized Boolean operators.
Filter design is conventionally performed using a wide variety of techniques. Thus, designing filters for processing images can be performed using statistical optimization techniques or expert knowledge. In filter design, as described above, a pair of training images is used, where one member of the training pair is the typically xe2x80x9cobserved image,xe2x80x9d and the other is the xe2x80x9cthe ideal image.xe2x80x9d The object of filter design is to map the xe2x80x9cobserved imagexe2x80x9d to a desired xe2x80x9cgenerated image.xe2x80x9d Depending on the sophistication of the filtering process, the generated image will more or less correspond to the ideal image. If the filtering process is very sophisticated, the generated image will correspond almost exactly to the ideal image. However, various constraints, such as cost, typically limit the sophistication of the filtering process.
Illustratively, FIG. 1 is a diagram illustrating a conventional technique for designing and using a template-based filter. The method may be directed to image tuning or appearance tuning, for example. The term appearance tuning refers to a lightening or darkening, i.e., density control, of a pixel in conjunction with the repositioning of the pixel relative to one or more neighborhood pixels.
FIG. 1 depicts an observed image 102, an ideal image 104, a template 106, and a generated image 108. The observed image 102 and the ideal image 104 represent, for example, a typical before and after set of images, respectively. In other words, the observed image 102 and the ideal image 104 are training images. The observed image 102 and the ideal image 104 may be actual images that are selected based on expert knowledge.
The observed image 102 and the ideal image 104 may be bitmaps, for example. In accordance with the conventional method for designing a filter, and the templates within the filter, the design method tries to map as accurately as possible the observed image 102 to an image that accurately correspond to the ideal image 104, given certain constraints, such as a limited number of templates. That is, the technique attempts to convert or transform the observed image 102 to the ideal image 104.
To further explain, the observed image 102 could be ideally converted or processed to an image identical to the ideal image 104 using an extensive set of templates and/or expert knowledge. Such a conversion would result in the best possible bitmap, which would correspond to the ideal image 104. However, it is typically not possible or desirable to use such an extensive set of templates in a filter. This is a result of constraints, such as memory capability and cost. Further, it should be recognized that it is simply not necessary to transform the observed image 102 to an image that exactly corresponds to the ideal image 104. That is, the human visual perception has shortcomings. Specifically, the human visual perception only detects certain components and aspects of a given image. Accordingly, while the ideal image 104 is the best possible corresponding representation of the observed image 102, this best possible representation may not be required, and probably is not required.
As shown in FIG. 1, in accord with this illustrative example, the generated image 108 is generated using the template 106. The generated image 108 may be generated without using an excessive number of templates or expert knowledge, depending on the requisite quality of the generated image 108. Further, optimally, generating the generated image 108 should minimize the generating cost, for example. Specifically, the generated image 108 only corresponds to the ideal image 104 in an optimized manner that focuses on details of the image that the human visual perception will actually detect.
In filter design processes, i.e., constructing a filter for subsequent use in other devices, for example, the typical method attempts to identify pixels or pixel patterns that are different between the generated image 106 and the ideal image 104. As more pixels are different, the pixel count difference between the generated image 106 and the ideal image 104 will increase. The templates that are chosen for inclusion in the filter 106 are those templates that minimize the pixel count difference between the generated image 108 and the ideal image 104. For example, the resolution of a document may be expressed in the form of spots per inch (spi). Further, it may be desirable or necessary to convert a 240 spi document bitmap to a 600 spi document bitmap, i.e., a document having greater resolution. A good filter is one that yields the generated image with the least possible number of pixels different from an ideal 600 spi bitmap, i.e., with the lowest pixel count difference.
Using conventional techniques, each of the difference pixels are considered equally. From the point of view of the systems and methods of this invention, the pixels conventionally are accorded equal weighting when computing the difference between the ideal and the filter generated image. The pixels are, in the sense of the systems and methods of this invention, all given a weighting of 1. As a result, the difference pixels are not analyzed in an optimum manner.
Accordingly, when various tasks such as resolution conversion, resolution enhancement, restoration, appearance tuning and de-screening are performed on grayscale or binary images, a template-based filter is often applied to the original image to convert it to a corresponding generated image. However, a shortcoming of conventionally designed template-based image processing filters is that the filters are not optimized relevant to a visual criterion. That is, conventional filters are not optimized with regard to the human visual perception. To explain, a xe2x80x9cdegradationxe2x80x9d in an image may be characterized as a pixel or group of pixels that adversely impact the quality of an image. Illustratively, the human eye is more sensitive to degradation along the vertical and horizontal axes, than along an axis 45xc2x0 to the vertical, i.e., an angled axis. Accordingly, these sensitivities of the human eye should be considered in an efficient manner, when designing a template-based filter. However, conventional design of template-based filters does not take into account the visual perception in an optimal manner.
Accordingly, this invention provides systems and methods that optimize template-based filter design in a manner that is relevant to the human visual system.
This invention provides systems and methods that optimize template-based filter design in a manner that is relevant to printing or other output in a particular operating environment.
This invention separately provides systems and methods that provide an improved technique to reduce the size of a template set to improve the cost efficiency of template-based filters.
This invention separately provides systems and methods that provide an optimized design for template-image processing filters for applications such as resolution conversion, resolution enhancement, image restoration, and the like.
This invention separately provides systems and methods that may be used in conjunction with known methods for resolution conversion, resolution enhancement, image restoration, and the like.
This invention separately provides systems and methods that may be used in conjunction with known filter design techniques to optimally yield images possessing better visual quality.
In one exemplary embodiment of the systems and methods of the invention, a template-based filter is designed by appropriately weighting pixels that are different between an image pair comprising an observed image and an ideal image. The difference pixels are weighted based on various factors associated with parameters of the image. The factors may be based on neighboring image structure in the observed image, the ideal image, or both.
In accordance with one embodiment, the systems and methods of the invention scan an observed image using an appropriate window. The window progresses from target pixel to target pixel in the observed image. At each target pixel, a windowed group of pixels is observed, i.e., a windowed neighborhood. Further, the pixels in the window are appropriately weighted based on the particular image being analyzed and the process to be performed on that image. In other words, the particular spatial location of a neighboring pixel in the windowed neighborhood will effect the weight that the properties of that neighboring pixel are accorded.
Further, in accordance with an embodiment of the systems and methods of the invention, all the weights associated with a selected target pixel in an observed image are summed, i.e., totaled. If the sum of the weights for the selected target pixel exceeds a predetermined threshold value, then the pixel pattern associated with that target pixel is, for example, chosen to be included in a look-up table. Further, the corresponding pattern in the ideal image is associated with the selected pixel pattern in the observed image. As a result, look-up table may be generated and subsequently used to convert an observed image to a generated image. The generated image corresponds to the ideal image, which was used in the creation of the look-up table, i.e., the creation of the template-based filter.
In this manner, the systems and methods of the invention attempt to minimize the sum of the weights associated with difference pixels between an observed image and an ideal image. As the sum of the weights decreases, the error associated with the conversion from an observed image to a generated image, which corresponds to an ideal image, also decreases. Illustratively, if the sum of the weights associated with the difference pixels were 0, then there would be no error associated with the conversion. That is, the generated image would exactly correspond to the ideal image upon implementation of the created look-up table.
Accordingly, the systems and methods of the invention recognize that some errors in a conversion process between an observed image and a generated image are more important than other errors. In accordance with the systems and methods of the invention, a weighting is assigned to various observed errors. The more important errors receive heavier weighting, while the less important errors receive a lighter weighting. Various criteria may be used to assign a specific weight value to an error.
A wide variety of weighting methods and techniques may be used in accordance with the invention based on the particular image or images to be filtered. One manner in which to assign appropriate weight is to determine which errors have a more visual impact than other errors. The errors which have a greater visual impact will receive a heavier weight. For example, an error which has a substantial visual impact associated with it may receive a weighting of 3. On the other hand, an error which has no or negligible visual impact associated with it may receive a weighting of 1, or even zero. Further, the threshold weighting of error may be predetermined to be 2. As a result, the template-based filter will be designed or created to contain a template to address the error with a weighting of 3, but not the error with a weighting of 1. Accordingly, the ultimate size of the created template-based filter is decreased, but the most important errors associated with the conversion from an observed image to a generated image are still addressed.
Accordingly, in some exemplary embodiments, the systems and methods of embodiments of the invention provide a method to decrease the cost of printer electronic hardware, for example, by designing a filter with a relatively small number of templates. The templates that are included in the filter will be provided based on only the most important potential errors. The templates chosen for the filter in accordance with the systems and methods of the invention modify the pixels with the most adverse visual impact.
These and other features and advantages of the systems and methods of this invention are described in or are apparent from the following detailed description of the exemplary embodiments.